/**
 * 
 */
package com.gwcloud.leetcode.tags.backtrace;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName   : Leetcode526 
 * @author      : ganwei 
 * @date        : 2020年5月12日
 * @Description : Leetcode526 优美的排列
 */
public class Leetcode0526 {
	int result = 0;
	/**
	 * -回溯
	 */
    public int countArrangement(int N) {

    	backtrack(N, new ArrayList<Integer>());
    	
    	return result;
    }
    /**
     * -回溯主题
     */
    public void backtrack(int N, List<Integer> il) {
    	if(il.size() == N) {
    		result += 1;
    		return;
    	}
    	
    	for(int i = 1; i <= N; i++) {
    		if(il.contains(i)) {
    			continue;
    		}
    		
    		int p = il.size()+1;
    		
    		if(i % p != 0 && p % i != 0) {
    			continue;
    		}
    		il.add(i);
    		backtrack(N,il);
    		il.remove(il.size()-1);
    		
    	}
    	
    }
    public static void main(String[] args) {
    	Leetcode0526 l526 = new Leetcode0526();
    	
    	System.out.println(l526.countArrangement(2));
    }
}
